package easy

/*
1.构造邻接表(二维切片edges, edges[i]存储的是节点i所连接的下一个节点)
2.先处理当前节点，然后遍历当前节点的邻接节点，每次循环都对i的邻接节点进行dfs
*/

func numWays(n int, relation [][]int, k int) (ans int) {
	edges := make([][]int, n)
	// 1.构建邻接表
	for _, v := range relation {
		edges[v[0]] = append(edges[v[0]], v[1])
	}

	count := 0
	var dfs func(int, int)
	dfs = func(x int, step int) {
		// 2.先处理当前节点，写出dfs的退出条件(步数达到k步)
		if step == k {
			if x == n-1 {
				count++
			}
			return
		}
		for _, v := range edges[x] {
			dfs(v, step+1)
		}
	}
	dfs(0, 0)
	return count
}
